B19 - Knapsack 2
https://atcoder.jp/contests/dp/tasks/dp_e
提出
code: python
n, w = map(int, input().split())
wv = list(map(int, input().split())) for _ in range(n)
# dpij := i 個までで、重さが j までの価値の最大
dp =[0 * (w+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, w+1):
dpi
解答
code: python
n, w = map(int, input().split())
wv = list(map(int, input().split())) for _ in range(n)
# dpij := i 個までで、価値が j までの重さの最小
dp = [10 ** 15 * 100001 for _ in range(n+1)]
dp00 = 0
for i in range(1, n+1):
for j in range(100001):
weight, value = wvi-1
if j < value:
dpij = dpi-1j
if j >= value:
dpij = min(dpi-1j, dpi-1j-value+weight)
ans = 0
for value in range(100001):
if dpnvalue <= w:
ans = value
print(ans)